package 中等.树;

import java.util.ArrayList;
import java.util.List;

/**
 * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符
 * 串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
 * 请你实现 Trie 类：
 * Trie() 初始化前缀树对象。
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 *  
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
 */
public class 实现Trie前缀树_208 {

    public static void main(String[] args) {

        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));

    }

}

/**
 * 并不需要为对象创建一个value属性
 * 由于仅由小写字母组成，其子孩子用一个26个trie节点的数组来存储，
 * 如果curNode==null，那么不存在
 */
class Trie {

    public boolean end;

    public Trie[] children;

    public Trie() {
        children = new Trie[26];
    }

    public void insert(String word) {
        char[] letters = word.toCharArray();
        Trie curTree = this;

        for (int i = 0; i < letters.length; i++) {
            Trie nextTree;
            // 当前树层的字母没有对应的字符
            if (curTree.children[letters[i] - 'a'] == null) {
                nextTree = new Trie();
                curTree.children[letters[i] - 'a'] = nextTree;
            } else {  // 存在字母
                nextTree = curTree.children[letters[i] - 'a'];
            }
            curTree = nextTree;
        }
        // 最后一个字母需要做标记
        curTree.end = true;
    }

    public boolean search(String word) {
        Trie lastTree = findLastTree(word);
        return lastTree != null && lastTree.end;
    }

    public boolean startsWith(String prefix) {
        return findLastTree(prefix) != null;
    }

    /**
     * 查询是否有单词的开始到单词的结束全部字母
     * 如果有返回最后一个字母对象
     *
     * @return
     */
    public Trie findLastTree(String prefix) {
        char[] letters = prefix.toCharArray();
        Trie curTree = this;
        for (int i = 0; i < prefix.length(); i++) {
            Trie nextTree = curTree.children[letters[i] - 'a'];
            if (nextTree == null) {
                return null;
            }
            curTree = nextTree;
        }
        return curTree;
    }

}

class Trie1 {

    public Trie1 root;

    public char value;

    public boolean end;

    public List<Trie1> children = new ArrayList<>();

    public Trie1() {
    }

    public Trie1(char value) {
        this.value = value;
    }

    public void insert(String word) {
        if (root == null) {
            root = new Trie1();
        }
        char[] chars = word.toCharArray();
        List<Trie1> curChildren = root.children;

        for (int i = 0; i < chars.length; i++) {
            boolean flag = false;
            for (Trie1 curNode : curChildren) {  //当前层的元素是否有对应的字符
                if (chars[i] == curNode.value) {
                    flag = true;
                    curChildren = curNode.children;
                    if (i == chars.length - 1) {  //字符串的结尾元素做个标记
                        curNode.end = true;
                    }
                    break;
                }
            }
            if (!flag) {
                Trie1 curNode = new Trie1(chars[i]);
                if (i == chars.length - 1) {
                    curNode.end = true;
                }
                curChildren.add(curNode);
                curChildren = curNode.children;
            }
        }

    }

    public boolean search(String word) {
        if (root == null) {
            return false;
        }
        List<Trie1> curChildren = root.children;
        for (int i = 0; i < word.length(); i++) {
            boolean flag = false;
            for (Trie1 curNode : curChildren) {
                if (curNode.value == word.charAt(i)) {
                    flag = true;
                    curChildren = curNode.children;
                    if (i == word.length() - 1 && curNode.end) {  // 搜索必须是全部匹配
                        return true;
                    }
                    break;
                }
            }
            if (!flag) {
                return false;
            }
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        if (root == null) {
            return false;
        }
        List<Trie1> curChildren = root.children;
        for (int i = 0; i < prefix.length(); i++) {
            boolean flag = false;
            for (Trie1 curNode : curChildren) {
                if (curNode.value == prefix.charAt(i)) {
                    flag = true;
                    curChildren = curNode.children;
                    break;
                }
            }
            if (!flag) {
                return false;
            }
        }
        return true;
    }

}

/**
 * 优化
 * 不需要root节点
 * new 的tree对象即为root节点
 */
class Trie2 {

    public char value;

    public boolean end;

    public List<Trie2> children = new ArrayList<>();

    public Trie2() {
    }

    public Trie2(char value) {
        this.value = value;
    }

    public void insert(String word) {
        char[] chars = word.toCharArray();
        List<Trie2> curChildren = this.children;

        for (int i = 0; i < chars.length; i++) {
            boolean flag = false;
            for (Trie2 curNode : curChildren) {  //当前层的元素是否有对应的字符
                if (chars[i] == curNode.value) {
                    flag = true;
                    curChildren = curNode.children;
                    if (i == chars.length - 1) {  //字符串的结尾元素做个标记
                        curNode.end = true;
                    }
                    break;
                }
            }
            if (!flag) {
                Trie2 curNode = new Trie2(chars[i]);
                if (i == chars.length - 1) {
                    curNode.end = true;
                }
                curChildren.add(curNode);
                curChildren = curNode.children;
            }
        }

    }

    public boolean search(String word) {
        List<Trie2> curChildren = this.children;
        for (int i = 0; i < word.length(); i++) {
            boolean flag = false;
            for (Trie2 curNode : curChildren) {
                if (curNode.value == word.charAt(i)) {
                    flag = true;
                    curChildren = curNode.children;
                    if (i == word.length() - 1 && curNode.end) {  // 搜索必须是全部匹配
                        return true;
                    }
                    break;
                }
            }
            if (!flag) {
                return false;
            }
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        List<Trie2> curChildren = this.children;
        for (int i = 0; i < prefix.length(); i++) {
            boolean flag = false;
            for (Trie2 curNode : curChildren) {
                if (curNode.value == prefix.charAt(i)) {
                    flag = true;
                    curChildren = curNode.children;
                    break;
                }
            }
            if (!flag) {
                return false;
            }
        }
        return true;
    }

}